package com.arithmetic.basics;

import com.util.ListNode;

/**
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 * 示例 1：
 * 输入：head = [1,2,2,1]
 * 输出：true
 * 示例 2：
 * <p>
 * 输入：head = [1,2]
 * 输出：false
 * 提示：
 * <p>
 * 链表中节点数目在范围[1, 105] 内
 * 0 <= Node.val <= 9
 */
public class Day32 {
    /**
     * 这段代码用于判断一个单链表是否为回文结构。主要逻辑分为三步：
     * 1. 使用快慢指针找到链表中点；
     * 2. 将后半部分链表反转；
     * 3. 比较前半部分和反转后的后半部分节点值是否相等。
     * 其中方法用于实现链表的反转。
     */
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, low = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            low = low.next;
        }
        fast = head;
        low = reBack(low);
        while (low != null && low.val == fast.val) {
            low = low.next;
            fast = fast.next;
        }
        return low == null ? true : false;
    }

    public ListNode reBack(ListNode head) {
        ListNode pre = null, next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}
/*好的，我们来用更通俗易懂的方式解释一下这段代码在做什么。
这段代码的目的是判断一个**单链表**（就像一串珠子，每个珠子只连着下一个珠子）是不是**回文**的。回文的意思是，从前往后看和从后往前看，这串珠子的值是一样的，比如 `1 -> 2 -> 2 -> 1` 就是回文，而 `1 -> 2 -> 3 -> 1` 就不是。
代码主要分三步走：

1.  **找到链表的中间点**：
    *   它使用了两个“指针”（可以想象成两个探测器）`fast` 和 `low`，都从链表头 `head` 开始。
    *   `low` 每次只往前走一步，而 `fast` 每次往前走两步。
    *   当 `fast` 走到链表末尾（或者超出一点）时，`low` 正好停在链表的中间位置。
    *   这样就巧妙地找到了中点，而不需要先遍历一遍计算总长度。

2.  **把链表后半部分反转**：
    *   找到中点后，代码调用 [reBack](file://D:\Change\LearnSpace\likou\src\main\java\com\arithmetic\basics\Day32.java#L38-L47) 函数，把从 `low`（中点）开始的后半部分链表给反转过来。
    *   [reBack](file://D:\Change\LearnSpace\likou\src\main\java\com\arithmetic\basics\Day32.java#L38-L47) 函数的作用是：把 `1 -> 2 -> 3` 变成 `3 -> 2 -> 1`。它通过逐个调整节点的指向来实现。
    *   反转之后，`low` 指针就指向了反转后的后半部分链表的头。

3.  **比较前半部分和反转后的后半部分**：
    *   现在，`fast` 指针还在链表头 (`head`)，`low` 指针在反转后的后半部分链表头。
    *   代码开始同时移动这两个指针，一个从原链表头开始，一个从反转后的后半部分头开始，逐一比较它们指向的节点的值 ([val](file://D:\Change\LearnSpace\likou\src\main\java\com\util\ListNode.java#L3-L3)) 是否相等。
    *   如果发现任何一对值不相等，循环就会停止。
    *   如果 `low` 指针顺利地走到了反转后链表的末尾（变成了 `null`），那就说明前半部分和后半部分（反转后）完全一样，原链表就是回文的。
简单来说，就是**找到中点 -> 翻转后半部分 -> 前后比较**。*/
